#include<iostream>
#include<string.h>
#include<time.h>
#include<math.h>
#include<algorithm>
//定义模拟退火的参数
#define T_start 1000000.0  // 初始温度
#define T_end (1e-14)
#define q  0.97    // 退火系数
#define L 1000  //迭代次数
#define N 30  // 城市数量

int solution[N]; // 用于存放一个解

double city[N][2] = {
    {41,94},{37,84},{54,67},{25,62},{7,64},
    {2,99},{68,58},{71,44},{54,62},{83,69},
    {64,60},{18,54},{22,60},{83,46},{91,38},
    {25,38},{24,42},{58,69},{71,71},{74,78},
    {87,76},{18,40},{13,40},{82,7},{62,32},
    {58,35},{45,21},{41,26},{44,35},{4,50}
}; 

double distance(const double*, const double*); // 计算两个点的距离
double path_len(const int*);  // 计算路径长度

void  initial_solution();  //创建一个初始解
void create_solution(); // 产生新解

double distance(const double* city1, const double* city2)
{
    double x1 = *city1;
    double y1 = *(city1 + 1);
    double x2 = *(city2);
    double y2 = *(city2 + 1);
    double dis = sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
    return dis;
}

// 计算路径长度
double path_len(const int* arr)
{
    double path = 0; // 初始化路径长度
    int index = *arr; // 定位到第一个数字(城市序号)
    for (int i = 0; i < N - 1; i++)
    {
        int index1 = *(arr + i);
        int index2 = *(arr + i + 1);
        double dis = distance(city[index1 - 1], city[index2 - 1]);
        path += dis;
    }
    int last_index = *(arr + N - 1); // 最后一个城市序号
    int first_index = *arr; // 第一个城市序号
    double last_dis = distance(city[last_index - 1], city[first_index - 1]);
    path = path + last_dis;
    return path; // 返回总的路径长度
}

// 初始化函数
void initial_solution()
{
    for (int i = 0; i < N; i++)
        solution[i] = i + 1;  // 初始化一个解
}

// 此处采用随机交叉两个位置的方式产生新的解
void create_solution()
{
    double r1 = ((double)rand()) / (RAND_MAX + 1.0);
    double r2 = ((double)rand()) / (RAND_MAX + 1.0);
    int pos1 = (int)(N * r1); //第一个交叉点的位置
    int pos2 = (int)(N * r2);
    int temp = solution[pos1];
    solution[pos1] = solution[pos2];
    solution[pos2] = temp;   // 交换两个点
}

int main()
{
    srand((unsigned)time(NULL)); //初始化随机数种子
    time_t start, finish;
    start = clock(); // 计时
    double T;
    int count = 0; // 记录降温次数
    T = T_start; //初始温度
    initial_solution(); //产生初始解
    int pre_solution[N]; // 用于保存上个解

    double f1, f2, df; //f1为初始解目标函数值，f2为新解目标函数值，df为二者差值

    double r; // 0-1之间的随机数，用来决定是否接受新解
    while (T > T_end) { // 当温度低于结束温度时，退火结束
        for (int i = 0; i < L; i++)
        {
            memcpy(pre_solution, solution, N * sizeof(int)); // 复制数组
            create_solution(); // 产生新解
            f1 = path_len(pre_solution);
            f2 = path_len(solution);

            df = f2 - f1;
            // Metropolis准则

            if (df >= 0)
            {
                r = ((double)rand()) / (RAND_MAX);
                if (exp(-df / T) <= r) // 保留原来的解
                {
                    memcpy(solution, pre_solution, N * sizeof(int));
                }
            }
        }
    T *= q; // 降温
    count++;
}
    finish = clock(); // 退火过程结束
    double duration = ((double)(finish - start)) / CLOCKS_PER_SEC; // 计算时间
    printf("采用模拟退火算法，初始温度T_start=%.2f,降温系数q=%.2f,每个温度迭代%d次,共降温%d次，得到的TSP最优路径为:\n", T_start, q, L, count);
    for (int i = 0; i < N - 1; i++)  // 输出最优路径
    {
        if (i % 10 == 0) printf("\n");
        printf("%d--->", solution[i]);
    }
    printf("%d\n", solution[N - 1]);
    double len = path_len(solution); // 最优路径长度
    printf("路径长度为:%lf\n", len);
    printf("程序运行耗时:%lf秒.\n", duration);
    return 0;
}